package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 题目：
 * 
 * 给定一个字符串S，一个字符串数组L，找出S中所有这样的子串起点，该子串包含L中的所有元素。
 * 
 * 说明：
 * 
 * 1）L中存在重复的元素
 * 
 * 2）子串不允许间断，即子串从开始到找全L中的所有元素之前，子串中不允许包含L以外的东西，而且，即使当前处理的子串是L中含有的，但是前面已经找够了，
 * 这个多余的也是不合法的，若此时还有L中的其他元素没找到，从这个起点开始也是不成功的。
 * 
 * 3）L在S中出现的顺序不同考虑，任意顺序，只要全部存在就可以。
 * 
 * 分析：
 * 
 * 1）先对L中的所有元素做个统计，定义一个hash map<string, int> 型
 * 变量total，统计每个词出现的次数，另外定义一个同类型的has_find
 * ，用来记录到目前为止，已经找到的L中的元素情况，当全部找全的时候就找到了一个合法的起始点。然后将has_find清空，继续找。
 * 
 * 2）整体的框架与传统的字符串匹配一致，不同的是这里不要求顺序，所以似乎在S中不能加速移动。
 * 
 * @author Administrator 2016年9月12日 下午10:39:17
 * @param
 * @return
 */
public class SubstringWithConcatenationOfAllWords {

	public SubstringWithConcatenationOfAllWords() {
		// TODO Auto-generated constructor stub
	}

	public static ArrayList<Integer> findSubstring(String S, String[] L) {
		ArrayList<Integer> result=new ArrayList<Integer>();
		if(S.length()<1||L.length<1){
			return result;
		}
		HashMap<String,Integer> map=new HashMap<String,Integer>();
		for(int i=0;i<L.length;i++){
			if(map.containsKey(L[i])){
				map.put(L[i],map.get(L[i])+1);
			}else{
				map.put(L[i],1);
			}
		}
		int nums=L.length;
		int subStrLen=L[0].length();
		for(int i=0;i<=S.length()-nums*subStrLen;i++){
			int from=i;
			HashMap<String,Integer> temp=(HashMap<String, Integer>) map.clone();
			String str=S.substring(from,from+subStrLen);
			int count=0;
			while(temp.containsKey(str)&&temp.get(str)>0){
				temp.put(str, temp.get(str)-1);
				count++;
				from=from+subStrLen;
				if(from+subStrLen>S.length()){
					break;
				}
				str=S.substring(from,from+subStrLen);
			}
			if(count==nums){
				result.add(i);
			}
			
		}
		return result;
	}
	
	public static void main(String[] args) {
		String S="barfoothefoobarman";
		String[] L={"foo","bar"};
		System.out.println(findSubstring(S, L));
	}
}
